import java.util.*;

/**
* @description: 433. 最小基因变化
* @author hewei
* @date 2022/8/1 16:35
* @version 1.0
*/

public class MinMutation {

    public static void main(String[] args) {
        MinMutation minMutation = new MinMutation();
        System.out.println(minMutation.minMutation("AAAACCCC", "CCCCCCCC", new String[]{"AAAACCCA","AAACCCCA","AACCCCCA","AACCCCCC","ACCCCCCC","CCCCCCCC","AAACCCCC","AACCCCCC"}));
    }

    HashMap<String, List<String>> map;
    HashSet<String> set;
    String start;
    String end;
    int ans = Integer.MAX_VALUE;
    public int minMutation1(String start, String end, String[] bank) {
        if (bank.length == 0 && start.equals(end)) return 0;
        if (bank.length == 0) return -1;
        if (check(start, end)) return 1;
        map = new HashMap<>();
        set = new HashSet<>();
        this.start = start;
        this.end = end;
        for (int i = 0; i < bank.length; i++) {
            for (int j = 0; j < bank.length; j++) {
                if (check(bank[i], bank[j])) {
                    if (!map.containsKey(bank[i])) map.put(bank[i], new ArrayList<>());
                    map.get(bank[i]).add(bank[j]);
                }
            }
        }
        if (!map.containsKey(start)) {
            for (int i = 0; i < bank.length; i++) {
                if (check(bank[i], start)) {
                    if (!map.containsKey(start)) map.put(start, new ArrayList<>());
                    map.get(start).add(bank[i]);
                    if (!map.containsKey(bank[i])) map.put(bank[i], new ArrayList<>());
                    map.get(bank[i]).add(start);
                }
            }
        }
        process(start, 0);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public void process(String s, int count) {
        if (s.equals(end)) {
            ans = Math.min(ans, count);
            return;
        }
        set.add(s);
        List<String> list = map.get(s);
        for (String temp : list) {
            if (!set.contains(temp)) process(temp, count + 1);
        }
        set.remove(s);
    }

    public boolean check(String s1, String s2) {
        int count = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) ++count;
            if (count > 1) return false;
        }
        return count == 1;
    }

    public int minMutation(String start, String end, String[] bank) {
        Deque<String> queue = new LinkedList<>();
        HashSet<String> set = new HashSet<>(Arrays.asList(bank));
        HashSet<String> vis = new HashSet<>();
        if (!set.contains(end)) return -1;
        if (start.equals(end)) return 0;
        queue.add(start);
        vis.add(start);
        int ans = 0;
        while (!queue.isEmpty()) {
            ++ans;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                char[] chars = queue.poll().toCharArray();
                for (int j = 0; j < 8; ++j) {
                    char temp = chars[j];
                    for (char c : new char[]{'A', 'C', 'G', 'T'}) {
                        if (c != chars[j]) {
                            chars[j] = c;
                            String s = new String(chars);
                            chars[j] = temp;
                            if (set.contains(s) && !vis.contains(s)) {
                                if (s.equals(end)) return ans;
                                queue.add(s);
                                vis.add(s);
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
}
